package com.ting.test.algorithms.二叉树;

/**
 * 平衡二叉树的概念:
 * 1. 左右子树的高度差不能大于1
 * 2. 每一个ke子树都是平衡二叉树
 * <p>
 * 利用递归的思想
 */
public class 判断是平衡二叉树 {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(2);
        Info info = process(head);
        System.out.println(info.isBalanced);
    }

    private static Info process(TreeNode node) {
        //base case
        if (node == null) {
            //默认空节点的高度为0，是平衡二叉树
            return new Info(true, 0);
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);

        boolean isBalanced = true;
        if (!leftInfo.isBalanced) {
            isBalanced = false;
        }
        if (!rightInfo.isBalanced) {
            if (!leftInfo.isBalanced) {
                isBalanced = false;
            }
        }

        if (Math.abs(leftInfo.height - rightInfo.height) > 1) {
            isBalanced = false;
        }

        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        return new Info(isBalanced, height);
    }


    static class Info {
        boolean isBalanced;
        int height;

        public Info(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }

}
